package qjc.h_二叉树;

import com.二叉树.练习题.TreeNode;

import java.util.Arrays;

public class h12_从前序与中序遍历构造二叉树 {
    /**
     * 递归终止条件：如果前序或中序为空，说明当前子树为空,
     * 前序第一个元素就是当前子树的根节点值,
     * 在中序数组中查找根节点的位置,根据位置切分左右两部分
     *
     * @param preorder
     * @param inorder
     * @return
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) {
            return null;
        }
        int rootValue = preorder[0];
        TreeNode root = new TreeNode(rootValue);
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootValue) {
                int[] inorderLeft = Arrays.copyOfRange(inorder, 0, i);
                int[] inorderRight = Arrays.copyOfRange(inorder, i + 1, inorder.length);
                int[] preLeft = Arrays.copyOfRange(preorder, 1, i + 1);
                int[] preRight = Arrays.copyOfRange(preorder, i + 1, preorder.length);
                root.left = buildTree(preLeft, inorderLeft);
                root.right = buildTree(preRight, inorderRight);
                break;
            }
        }
        return root;
    }
}
